A data processing system typically comprises a host computer connected to one or more nodes, e.g., other host computers or peripheral devices, via an interconnect medium. The host computer comprises a number of basic elements including a central processing unit (CPU), a host memory and an input/output (I/O) port adapter that physically connects the computer to the interconnect medium. In general, the interconnect medium is typically a network or I/O bus, and the peripheral devices are typically disks, tapes and communications equipment.
The computer is functionally organized by an operating system comprising a collection of software modules that control the execution of computer programs and manage the transfer of information among the elements of the computer. The host memory stores computer program information, i.e., data and instructions, in addressable storage locations. The CPU then executes the programs by fetching and interpreting the instructions, and processing the data in accordance with the instructions.
The operating system includes a port driver that controls the port adapter when performing I/O operations, such as the transfer of information between the host computer and a node. In order to efficiently perform these operations, the port driver and port adapter exchange messages, e.g., commands and responses. Specifically, the driver sends a command to the port adapter to perform an operation and the port adapter returns a response to the driver. To facilitate this exchange, the driver and adapter typically communicate via locations in the host memory that are accessible by both the port driver, i.e., the CPU, and the port adapter. These locations are organized to provide data structures such as rings or interlocked queues.
A ring structure is typically implemented in entries contained in contiguous memory locations. These locations are allocated by the port driver at system initialization. A synchronization mechanism, such as a bit within each ring entry or a set of pointers, is included to identify "ownership" by either the adapter or the driver. Specifically, the port driver inserts a command into an entry location and sets the ownership mechanism to indicate ownership by the port adapter. The port adapter eventually retrieves the command and then changes the ownership mechanism to indicate ownership by the driver. This informs the driver that the command has been retrieved by the port adapter and that another command may be inserted into that location. In essence, this is a removal of that entry from the ring.
Insertion and removal of entries occur in sequence, typically with the use of two pointers, i.e., one to identify the next entry to be retrieved and another to identify the next location for entry insertion. As a result, the driver and adapter typically operate on entries physically located close to one another and usually within the same memory block. This may lead to "cache" contention between the driver and port adapter if the port adapter attempts to copy the block into its own buffer memory.
Because of the contiguous memory location nature of the ring entries, the driver must allocate a sufficient number of ring entries during initialization. Specifically, if too many entries are allocated, memory is wasted; if too few entries are allocated, a temporary imbalance between the insertion and removal rates can cause ring overflow and slow down the execution of the port driver and other software components that use the ring.
In contrast to a ring structure, the entries of an interlocked queue do not necessarily occupy consecutive locations in host memory. Rather, each entry contains a forward link pointer indicating the memory location of the next entry in the queue. Therefore, the port driver may "dynamically expand" the size of the queue, i.e., allocate an additional queue entry, by inserting a pointer in the queue, indicating the location of a new entry. This does not stall computer operation or waste memory.
The interlocked queue also has a synchronization mechanism that allows either the port adapter or driver to "lock" or maintain ownership of a queue for the purpose of inserting or removing entries; the mechanism is typically an interlock bit that identifies ownership of the entry. However, the interlocked queue requires many host memory references to insert and remove the entries. In general, insertion of an entry into the queue requires at least five memory operations by the port adapter: two operations to perform an interlock of the queue header to set the interlock bit; at least one operation to adjust the various pointers of the entries in the queue; and two operations to perform another interlock to clear the bit in the queue header. These memory operations occur serially, thus providing a significant component of port adapter processing overhead.
Therefore, it is desirable to provide a communication queue apparatus having a structure and mechanics that avoid the foregoing difficulties by allowing concurrent insertion of entries by a first entity, such as either a port driver or an port adapter, and removal by the other entity without the need for an external synchronization mechanism.
In addition, it is desirable to provide a one-way communication interface between the entities that, in one aspect of the invention, minimizes the frequency with which one entity accesses the communication queue apparatus to exchange information with the other entity.
Furthermore, it is desirable to provide a two-way communication interface between the entities that, in another aspect of the invention, reduces the overhead associated with exchanging information between the entities.